package 简单算法;

import java.util.Arrays;

/**
 * @Author: 胡成
 * @Version: 0.0.1V
 * @Date: 2019-05-23
 * @Description: 给出 2 * n + 1个数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
 * 样例
 * 样例 1:
 * 输入：[1,1,2,2,3,4,4]
 * 输出：3
 * 解释：
 * 仅3出现一次
 * 样例 2:
 * 输入：[0,0,1]
 * 输出：1
 * 解释：
 * 仅1出现一次
 * 挑战
 * 一次遍历，常数级的额外空间复杂度
 * 注意事项
 * n≤100
 **/
public class 落单的数 {

    public static void main(String[] args) {
        落单的数 s = new 落单的数();
        System.out.println(s.singleNumber(new int[]{1,1,2,2,4,4,5,6,7,6,7,100,-1,-2,-1,100,3,-2,3}));
    }

    public int singleNumber(int[] A) {
        // write your code here
        Arrays.sort(A);
        int n = A[0];
        int i = 1;
        while (i < A.length) {
            if (n == A[i]) {
                n = A[++i];
                i++;
            }else{
                break;
            }
        }
        return n;
    }
}
